/**
* @description: 676. 实现一个魔法字典
* @author hewei
* @date 2022/8/11 15:27
* @version 1.0
*/

public class MagicDictionary {

    Trie node;
    public MagicDictionary() {
        node = new Trie();
    }

    public void buildDict(String[] dictionary) {
        for (int i = 0; i < dictionary.length; i++) {
            node.add(dictionary[i]);
        }
    }

    public boolean search(String searchWord) {
        return searchDfs(node, searchWord, 0, false);
    }

    public boolean searchDfs(Trie node, String searchWord, int i, boolean flag) {
        if (i == searchWord.length()) return flag && node.end > 0;

        char c = searchWord.charAt(i);
        if (node.next[c - 'a'] != null && searchDfs(node.next[c - 'a'], searchWord, i + 1, flag)) return true;
        if (flag) return false;
        for (int j = 0; j < 26; j++) {
            if (j == c - 'a' || node.next[j] == null) continue;
            if (searchDfs(node.next[j], searchWord, i + 1, true)) return true;
        }
        return false;
    }

    class Trie {
        Trie[] next;
        int end;

        Trie() {
            next = new Trie[26];
            end = 0;
        }

        public void add(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (node.next[c - 'a'] == null) node.next[c - 'a'] = new Trie();
                node = node.next[c - 'a'];
            }
            node.end++;
        }
    }
}
